package node;

import java.util.*;

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x){
        this.val = x;
    }

    public static void main(String[] args) {
       ArrayList<Integer> arr = new ArrayList<>();
       arr.add(1);
       arr.add(2);
       arr.add(3);
       arr.add(0,4);
       arr.add(1,5);
       for (int a:arr){
           System.out.println(a);
       }


    }

    //两个非负整数保存在链表中，请返回相加后的结果


    public void reorderList(ListNode head) {
        while (head != null) {
            ListNode next = head.next;
            ListNode pre = ReverseList(next);
            head.next = pre;
            head = pre;
        }
    }

    /*
     * 反转一个链表 返回反转后的表头
     * */
    public static ListNode ReverseList(ListNode head) {
        ListNode next = null;
        ListNode pre =null;
        while (head != null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }


    //对链表进行排序   思路：从头到尾遍历，以每个遍历到的节点为开始，
    // 找到该节点后面最小的一个节点，如果比当前节点值小，则交换值
    public ListNode insertionSortList (ListNode head) {
        // write code here
        ListNode root = new ListNode(0);
        root.next = head;
        while (head!=null){
            ListNode res = getMinNode(head);
            if (res.val<head.val){
                int temp = res.val;
                res.val = head.val;
                head.val=temp;
            }
            head=head.next;
        }
        return root.next;
    }
    public static ListNode getMinNode(ListNode root){
        ListNode res = root;
        while (root!=null){
            if (root.val<res.val){
                res = root;
            }
            root=root.next;
        }
        return res;
    }

    public static ListNode rotateRight(ListNode head, int k) {
        if(head==null || k==0){
            return head;
        }
        ListNode temp = new ListNode(0);
        temp.next = head;
        int len = 1;
        while(head.next!=null){
            head =head.next;
            len++;
        }
        head.next = temp.next;
        k = k%len;
        ListNode newHead = temp.next;
        while(len-k>1){
            newHead = newHead.next;
            k++;
        }
        ListNode res = newHead.next;
        newHead.next = null;

        return res;
    }


    //合并两个有序链表
    public static ListNode mergeTwoLists1 (ListNode l1, ListNode l2) {
        // write code here
        ListNode temp = new ListNode(0);
        ListNode head = temp;
        while(l1!=null && l2!=null){
            if(l1.val>=l2.val){
                head.next = new ListNode(l1.val);
                l1 = l1.next;
                head = head.next;
            }else{
                head.next = new ListNode(l2.val);
                l2 = l2.next;
                head = head.next;
            }
        }
        if(l2!=null){
            head.next= l2;
        }
        if(l1!=null){
            head.next= l1;
        }
        return temp.next;
    }

    public boolean isPalindrome (ListNode head) {
        // write code here
        if (head == null || head.next==null){
            return true;
        }

        ListNode f1 = endOfFirstHalf(head);
        ListNode f2 = reverList(f1.next);
        ListNode p1 = head;
        ListNode p2 = f2;
        boolean res = true;
        while (res && p2!=null){
            if (p1.val !=p2.val){
                return false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        f1.next = reverList(f2);
        return res;

    }

    public ListNode reverList(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while (cur!=null){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

    public ListNode endOfFirstHalf(ListNode head){
        ListNode f = head;
        ListNode s = head;
        while (f.next!=null && f.next.next!=null){
            f = f.next.next;
            s=s.next;
        }
        return s;
    }


    //将已经移除的盒子赋值-1   函数返回值表示当前剩余盒子可以获得的最大积分
    public static int removeBoxes(int[] boxes) {
        //对于剩余没有移除的连续区间  进行轮询  求移除其可获得得最大值
        ArrayList<Integer> arr = arrToList(boxes);
        return remoceBoxes(arr);
    }

    public static ArrayList<Integer> arrToList(int[] arr){
        ArrayList<Integer> ar  =  new ArrayList<>();
        for (int a: arr){
            ar.add(a);
        }
        return ar;
    }

    public static int remoceBoxes(ArrayList<Integer> arrayList){
        if (arrayList.size()==0){
            return 0;
        }
        int res = 0;
        for (int a=0;a<arrayList.size();a++){
            ArrayList<Integer> arr = new ArrayList<>(arrayList);
            int num = 1;
            int b=a;
            int temp = arr.remove(a);
            System.out.println(a+" |  " +arr.get(a));
            while (temp == arr.get(a)&&arr.size()>0){
            System.out.println(a+"   " +arr.get(a));
                arr.remove(a);
                num++;
                b++;
            }
            res = Math.max(res,(int)Math.pow(num,2)+remoceBoxes(arr));
            a=b;
        }
        return res;
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode temp = new ListNode(0);
        ListNode t = temp;
        while (l1!=null || l2!=null){
            int v1 = l1==null?Integer.MAX_VALUE:l1.val;
            int v2 = l2==null?Integer.MAX_VALUE:l2.val;
            if (v1<v2){
                temp.next = new ListNode(l1.val);
                l1=l1.next;
            }else {
                temp.next = new ListNode(l2.val);
                l2=l2.next;
            }
            temp = temp.next;
        }
        return t;
    }

    //删除倒数第n个元素
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode temp = new ListNode(0);
        temp.next = head;
        ListNode fast = temp;
        ListNode slow = temp;
        while (n > 0) {
            fast = fast.next;
            n--;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return temp.next;
    }


    //输出链表中倒数第k个节点
    public ListNode FindKthToTail(ListNode head,int k) {
        if (k<0 || head ==null){
            return null;
        }
        ArrayList<ListNode> arr  =  new ArrayList<>();
        int len = 0;
        while (head!=null){
            arr.add(head);
            len++;
            head = head.next;
        }

        return  arr.get(len-k-1);
    }


    /*
    * 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
    * */
    public ListNode Merge(ListNode list1,ListNode list2) {
        if (list1 ==null && list2 == null){
            return null;
        }
        if (list1 == null){
            return list2;
        }
        if (list2 == null){
            return list1;
        }
        int a = list1.val;
        int b =list2.val;
        ListNode head = null;
        if (a<=b){
            head = new ListNode(a);
            list1 = list1.next;
        }else {
            head = new ListNode(b);
            list2= list2.next;
        }
        head.next = Merge(list1,list2);
        return head;
    }

    /*
    * 显示两个链表的第一个公共节点
    * */
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        HashSet<ListNode> set = new HashSet<>();
        while (pHead1!=null){
            set.add(pHead1);
            pHead1 = pHead1.next;
        }
        while (pHead2!=null){
            if (set.contains(pHead2)){
                return pHead2;
            }
            pHead2 = pHead2.next;
        }
        return null;
    }

    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        HashSet<ListNode> set = new HashSet<>();
        ListNode res = null;
        while(pHead.next!=null){
            if (set.contains(pHead)){
                res = pHead;
                return res;
            }
            set.add(pHead);
            pHead = pHead.next;
        }
        return res;
    }
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode root = new ListNode(0);
        ListNode cursor = root;
        int carry = 0;
        while(l1 != null || l2 != null || carry != 0) {
            int l1Val = l1 != null ? l1.val : 0;
            int l2Val = l2 != null ? l2.val : 0;
            int sumVal = l1Val + l2Val + carry;
            carry = sumVal / 10;

            ListNode sumNode = new ListNode(sumVal % 10);
            cursor.next = sumNode;
            cursor = sumNode;

            if(l1 != null) l1 = l1.next;
            if(l2 != null) l2 = l2.next;
        }

        return root.next;
    }
}
